package sortingAdvance.mergeSortAdvance;

import sortingAdvance.mergeSort.SortTestHelper;

import java.util.Arrays;

/**
 * 归并排序nlogn级别排序算法，核心是递归成logn层级，每一层级使用on级别排序
 * mxf
 * 2018年5月20日17:00:04
 */
public class MergeSort {

    public static void sort(Comparable[] arr) {
        int length = arr.length;
        sort(arr, 0, length - 1);
    }

    /**
     * 逐层级进行递归，最后进行归并
     * @param arr
     * @param l
     * @param r
     */
    private static void sort(Comparable[] arr, int l, int r) {
        if (l >= r)
            return;

        int mid = (l + r) / 2;
        sort(arr, l, mid);
        sort(arr, mid+1, r);
        merge(arr, l, mid, r);
    }

    /**
     * 归并
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    private static void merge(Comparable[] arr, int l, int mid, int r) {
        int m = l;
        int n = mid + 1;
        Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);// 开辟一个临时空间, 不包含to位置的元素

        for(int i = l; i <= r; i++) {
            if(m > mid) {
                arr[i] = aux[n - l];
                n++;
            } else if(n > r) {
                arr[i] = aux[m - l];
                m++;
            } else if(aux[m - l].compareTo(aux[n - l]) > 0) {
                arr[i] = aux[n - l];
                n++;
            } else {
                arr[i] = aux[m - l];
                m++;
            }
        }
    }

    // 测试MergeSort
    public static void main(String[] args) {

        // Merge Sort是我们学习的第一个O(nlogn)复杂度的算法
        // 可以在1秒之内轻松处理100万数量级的数据
        // 注意：不要轻易尝试使用SelectionSort, InsertionSort或者BubbleSort处理100万级的数据
        // 否则，你就见识了O(n^2)的算法和O(nlogn)算法的本质差异：）
        int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 1000000);
        SortTestHelper.testSort("sortingAdvance.mergeSort.MergeSort", arr);
        //SortTestHelper.printArray(arr);
        return;
    }


}
